home *** CD-ROM | disk | FTP | other *** search
/ Disc to the Future 2 / Disc to the Future Part II Programmer's Reference (Wayzata Technology)(6013)(1992).bin / MAC / MPW_TOOL / TOOLS / TOOLS_WI / ICON_8 / ICONX_FO / RMEMEXP.C < prev    next >
Text File  |  1990-03-11  |  13KB  |  445 lines
  1. /*
  2.  * File: rmemexp.c - memory management functions for expandable regions
  3.  *  Contents: initalloc, reclaim, malloc, calloc, free
  4.  */
  5.  
  6.  
  7. /*
  8.  * Prototypes.
  9.  */
  10.  
  11. hidden    novalue moremem    Params((uword units));
  12. hidden    novalue    reclaim    Params((int region));
  13.  
  14. word xcodesize;
  15.  
  16. /*
  17.  * initalloc - initialization routine to allocate memory regions
  18.  */
  19.  
  20. novalue initalloc(codesize)
  21. word codesize;
  22.    {
  23.    xcodesize = codesize;
  24.  
  25.    /*
  26.     * Establish icode region
  27.     */
  28.    code = (char *)sbrk((word)0);
  29.  
  30.    /*
  31.     * Set up allocated memory.    The regions are:
  32.     *
  33.     *    Static memory region
  34.     *    Allocated string region
  35.     *    Allocate block region
  36.     *    Qualifier list
  37.     */
  38.  
  39.    statfree = statbase = (char *)((uword)(code + codesize + 3)  & ~03);
  40.  
  41. /*
  42.  * The following code is operating-system dependent [@rmemexp.01].  Set end of
  43.  *  static region, rounding up if necessary.
  44.  */
  45.  
  46. #if PORT
  47.    statend = (char *)(((uword)statbase) + mstksize + statsize);
  48. Deliberate Syntax Error
  49. #endif                    /* PORT */
  50.  
  51. #if AMIGA || HIGHC_386 || MVS || OS2 || VM
  52.    /* uses FixedRegions */
  53. #endif                    /* AMIGA  || HIGHC_386 || ... */
  54.  
  55. #if MSDOS
  56.    statend =
  57.       (char *)(((uword)statbase) + (((mstksize + statsize + 511)/512) * 512));
  58. #endif                    /* MSDOS */
  59.  
  60. #if MACINTOSH
  61. #if MPW
  62.    statend = (char *)(((uword)statbase) + mstksize + statsize);
  63. #endif                    /* MPW */
  64. #endif                    /* MACINTOSH */
  65.  
  66. #if ATARI_ST || UNIX || VMS
  67.    statend = (char *)(((uword)statbase) + mstksize + statsize);
  68. #endif                    /* ATARI_ST || UNIX || VMS */
  69.  
  70. /*
  71.  * End of operating-system specific code.
  72.  */
  73.  
  74.    strfree = strbase = (char *)((uword)(statend + 63) & ~077);
  75.    blkfree = blkbase = strend = (char *)((((uword)strbase) + ssize +
  76.       63) & ~077);
  77.    equallist = (dptr *)(blkend =
  78.       (char *)((((uword)(blkbase) + abrsize + 63)) & ~077));
  79.  
  80.    /*
  81.     * Try to move the break back to the end of memory to allocate (the
  82.     *  end of the string qualifier list) and die if the space isn't
  83.     *  available.
  84.     */
  85.    if ((int)brk((char *)equallist) == -1)
  86.       error("insufficient memory");
  87.    currend = (char *)sbrk((word)0);    /* keep track of end of memory */
  88.    }
  89.  
  90. /*
  91.  * reclaim - reclaim space in the allocated memory regions. The marking
  92.  *  phase has already been completed.
  93.  */
  94.  
  95. static novalue reclaim(region)
  96. int region;
  97. {
  98.    register word stat_extra, str_extra, blk_extra;
  99.    register char *newend;
  100.  
  101.    stat_extra = 0;
  102.    str_extra = 0;
  103.    blk_extra = 0;
  104.  
  105.    /*
  106.     * Collect available co-expression blocks.
  107.     */
  108.    cofree();
  109.  
  110.    /*
  111.     * If there was no room to construct the qualifier list, the string
  112.     *  region cannot be collected and the static region cannot be expanded.
  113.     */
  114.    if (!qualfail) {
  115.       /*
  116.        * Check whether the static region needs to be expanded. Regions cannot
  117.        *  be expanded if someone else has moved the end of allocated storage.
  118.        */
  119.       if (statneed && currend == sbrk((word)0)) {
  120.          /*
  121.           * Make sure there is space for the requested static region expansion.
  122.           *  The check involving equallist and newend appears to only be
  123.           *  required on machines where the above addition of statneed might
  124.           *  overflow.
  125.           */
  126.          newend = (char *)equallist + statneed;
  127.          if ((uword)newend >= (uword)(char *)equallist &&
  128.              (int)brk((char *)newend) != -1) {
  129.                stat_extra = statneed;
  130.                statneed = 0;
  131.                statend += stat_extra;
  132.                equallist = (dptr *)newend;
  133.                currend = sbrk((word)0);
  134.                }
  135.          }
  136.    
  137.       /*
  138.        * Collect the string space, indicating that it must be moved back
  139.        *  extra bytes.
  140.        */
  141.       scollect(stat_extra);
  142.    
  143.       if (region == Strings && currend == sbrk((word)0)) {
  144.          /*
  145.           * Calculate a value for extra space.  The value is (the larger of
  146.           *  (twice the string space needed) or (a quarter of the string space))
  147.           *  minus the unallocated string space.
  148.           */
  149.          str_extra = (Max(2*strneed, ((uword)strend - (uword)strbase)/4) -
  150.                ((uword)strend - (uword)strfree) + (GranSize-1)) & ~(GranSize-1);
  151.          while (str_extra > 0) {
  152.             /*
  153.              * Try to get str_extra more bytes of storage.  If it can't be
  154.              *  gotten, decrease the value by GranSize and try again.  If
  155.              *  it's gotten, move back equallist.
  156.              */
  157.             newend = (char *)equallist + str_extra;
  158.             if ((uword)newend >= (uword)(char *)equallist &&
  159.                 (int)brk((char *)newend) != -1) {
  160.                    equallist = (dptr *) newend;
  161.                    currend = sbrk((word)0);
  162.                    break;
  163.                    }
  164.             str_extra -= GranSize;
  165.             }
  166.          if (str_extra < 0)
  167.             str_extra = 0;
  168.          }
  169.       }
  170.  
  171.    /*
  172.     * Adjust the pointers in the block region.
  173.     */
  174.    adjust(blkbase, blkbase + stat_extra + str_extra);
  175.  
  176.    /*
  177.     * Compact the block region.
  178.     */
  179.    compact(blkbase);
  180.  
  181.    if (region == Blocks && currend == sbrk((word)0)) {
  182.       /*
  183.        * Calculate a value for extra space.  The value is (the larger of
  184.        *  (twice the block region space needed) or (one quarter of the
  185.        *  block region)) plus the unallocated block space.
  186.        */
  187.       blk_extra = (Max(2*blkneed, ((uword)blkend - (uword)blkbase)/4) -
  188.                ((uword)blkend - (uword)blkfree) + (GranSize-1)) & ~(GranSize-1);
  189.       while (blk_extra > 0) {
  190.          /*
  191.           * Try to get blk_extra more bytes of storage.  If it can't be gotten,
  192.           *  decrease the value by GranSize and try again.  If it's gotten,
  193.           *  move back equallist.
  194.           */
  195.          newend = (char *)equallist + blk_extra;
  196.          if ((uword)newend >= (uword)(char *)equallist &&
  197.              (int)brk((char *)newend) != -1) {
  198.                 equallist = (dptr *) newend;
  199.                 currend = sbrk((word)0);
  200.                 break;
  201.                 }
  202.          blk_extra -= GranSize;
  203.          }
  204.       if (blk_extra < 0)
  205.          blk_extra = 0;
  206.    }
  207.                 
  208.    if (stat_extra + str_extra > 0) {
  209.       /*
  210.        * The block region must be moved.  There is an assumption here that the
  211.        *  block region always moves up in memory, i.e., the static and
  212.        *  string regions never shrink.    With this assumption in hand,
  213.        *  the block region must be moved before the string space lest the
  214.        *  string space overwrite block data.  The assumption is valid,
  215.        *  but beware if shrinking regions are ever implemented.
  216.        */
  217.       mvc((uword)blkfree - (uword)blkbase, blkbase, blkbase + stat_extra +
  218.          str_extra);
  219.       blkbase += stat_extra + str_extra;
  220.       blkfree += stat_extra + str_extra;
  221.       }
  222.    blkend += stat_extra + str_extra + blk_extra;
  223.  
  224.    if (stat_extra > 0) {
  225.       /*
  226.        * The string space must be moved up in memory.
  227.        */
  228.       mvc((uword)strfree - (uword)strbase, strbase, strbase + stat_extra);
  229.       strbase += stat_extra;
  230.       strfree += stat_extra;
  231.       }
  232.    strend += stat_extra + str_extra;
  233.    }
  234.  
  235. /*
  236.  * These are Icon's own versions of the allocation routines.  They are
  237.  *  not used for the fixed-regions versions of memory management.  They
  238.  *  normally overload the corresponding library routines. If this is not
  239.  *  possible, they are re-named and calls to them are renamed.
  240.  */
  241.  
  242. static HEADER base;        /* start with empty list */
  243. static HEADER *allocp = NULL;    /* last allocated block */
  244.  
  245. pointer malloc(nbytes)
  246. msize nbytes;
  247.    {
  248.    register HEADER *p, *q;
  249.    register uword nunits;
  250.    register pointer xbase;
  251.    int attempts;
  252.  
  253.    if (statbase == NULL) {
  254.      if ((xbase = sbrk(nbytes)) == (pointer)-1)
  255.         syserr("malloc: failed during startup");
  256.      return xbase;
  257.      }
  258.  
  259.    nunits = 1 + (nbytes + sizeof(HEADER) - 1) / sizeof(HEADER);
  260.  
  261.    if ((q = allocp) == NULL) {    /* no free list yet */
  262.       base.s.ptr = allocp = q = &base;
  263.       base.s.bsize = 0;
  264.       }
  265.  
  266.    for (attempts = 2; attempts--; q = allocp) {
  267.       for (p = q->s.ptr;; q = p, p = p->s.ptr) {
  268.          if (p->s.bsize >= nunits) {    /* block is big enough */
  269.             if (p->s.bsize == nunits)    /* exactly right */
  270.                q->s.ptr = p->s.ptr;
  271.             else {            /* allocate tail end */
  272.                p->s.bsize -= nunits;
  273.                p += p->s.bsize;
  274.                p->s.bsize = nunits;
  275.                }
  276.             allocp = q;
  277.  
  278. #ifdef MemMon
  279.             if (nunits > 1)   {
  280.                MMStat((char *)(p + 1), (word) nbytes, 'A');
  281.                *(int *)(p + 1) = 0;    /* clear FREEMAGIC flag */
  282.                }
  283. #endif                    /* MemMon */
  284.  
  285.             return (char *)(p + 1);
  286.             }
  287.          if (p == allocp) {    /* wrap around */
  288.             moremem(nunits);    /* garbage collect and expand if needed */
  289.             break;
  290.             }
  291.          }
  292.       }
  293.  
  294.       return NULL;
  295.    }
  296.  
  297. #define FREESIZE 2    /* units sizeof(HEADER) that justify free() */
  298.  
  299. /*
  300.  *  realloc() allocates a block of memory of a requested size (amount) to
  301.  *  contain the contents of the current block (curmem) or as much as will
  302.  *  fit.  Blocks are allocated in units of sizeof(HEADER)
  303.  */
  304.  
  305. pointer realloc(curmem,newsiz)
  306. register pointer curmem;        /* the current memory pointer */
  307. msize newsiz;                /* bytes needed for new allocation */
  308.    {
  309.    register int cunits;        /* currently allocated units */
  310.    register int nunits;        /* new units required */
  311.    char *newmem;        /* the new memory pointer */
  312.    register HEADER *head;    /* all blocks used or free have a header */
  313.  
  314.    /*
  315.     * First establish the unit sizes involved.
  316.     */
  317.  
  318.    nunits = 1 + (newsiz + sizeof(HEADER) - 1) / sizeof(HEADER);
  319.    head = ((HEADER *)curmem) - 1;    /* move back a block header */
  320.    cunits = (int)head->s.bsize;
  321.  
  322.    /*
  323.     * Now allocate or free space as required.
  324.     */
  325.  
  326.    if (nunits <= cunits) {    /* we already have the space */
  327.       if (cunits - nunits < FREESIZE)
  328.          return curmem;
  329.       else {            /* free space at end of current block */
  330.          head->s.bsize = nunits;    /* reduce space used */
  331.          head += nunits;        /* move to free space */
  332.          head->s.bsize = cunits - nunits;
  333.          free((pointer)(++head));    /* free this new block */
  334.          return curmem;
  335.          }
  336.       }
  337.    else {                /* more space needed */
  338.       if ((newmem = malloc((msize)newsiz)) != NULL) {
  339.          memcopy(newmem,curmem,(word)((cunits - 1) * sizeof(HEADER)));
  340.          free(curmem);
  341.          return newmem;
  342.          }
  343.       }
  344.    return NULL;
  345.    }
  346.  
  347. /*
  348.  * calloc() allocates ecnt number of esiz-sized chunks of zero-initialized
  349.  * memory for an array of ecnt elements.
  350.  */
  351.  
  352. pointer calloc(ecnt,esiz)
  353.    register msize ecnt, esiz;
  354.    {
  355.    register char *mem;            /* the memory pointer */
  356.    register msize amount;        /* the amount of memory needed */
  357.  
  358.    amount = ecnt * esiz;
  359.    if ((mem = malloc(amount)) != NULL) {
  360.       memfill(mem,0,(word)amount);        /* initialize it to zero */
  361.       return mem;
  362.       }
  363.    return NULL;
  364.    }
  365.  
  366. static novalue moremem(nunits)
  367. uword nunits;
  368.    {
  369.    register HEADER *up;
  370.    register word rnu;
  371.    word n;
  372.  
  373.    rnu = NALLOC * ((nunits + NALLOC - 1) / NALLOC);
  374.    n = rnu * sizeof(HEADER);
  375.    if (((uword)statfree) + n > (uword)statend) {
  376.       statneed = ((n / statincr) + 1) * statincr;
  377.       coll_stat++;
  378.       collect(Static);
  379.       }
  380.    /*
  381.     * See if there is any room left.
  382.     */
  383.    if ((uword)statend - (uword)statfree > sizeof(HEADER)) {
  384.       up = (HEADER *) statfree;
  385.       up->s.bsize = ((uword)statend - (uword)statfree) / sizeof(HEADER);
  386.       statfree = (char *) (up + up->s.bsize);
  387.       free((pointer)(up + 1));    /* add block to free memory */
  388.       }
  389.    }
  390.  
  391. #if LATTICE || LSC
  392. #define nothing 0
  393. int free(ap)
  394. #else                    /* LATTICE || LSC */
  395. #define nothing
  396. novalue free(ap)        /* return block pointed to by ap to free list */
  397. #endif                    /* LATTICE || LSC */
  398. pointer ap;
  399.    {
  400.    register HEADER *p, *q;
  401.  
  402. /* free may be called to free a block before the static region is
  403.  *  initialized.
  404.  */
  405.    if (statbase == (char *)NULL || (char *)ap < statbase)
  406.       return nothing;
  407.  
  408.    p = (HEADER *)ap - 1;    /* point to header */
  409.  
  410. #ifdef MemMon
  411.    if (p->s.bsize > 1)    {
  412.       if (*(int *)(p + 1) != T_Coexpr)
  413.          MMStat((char *)ap, (word)((p->s.bsize - 1) * sizeof(HEADER)), 'F');
  414.       *(int *)(p + 1) = FREEMAGIC;
  415.       }
  416. #endif                    /* MemMon */
  417.  
  418.    if (p->s.bsize * sizeof(HEADER) >= statneed)
  419.      statneed = 0;
  420.    for (q = allocp; !((uword)p > (uword)q && (uword)p < (uword)q->s.ptr);
  421.       q = q->s.ptr)
  422.          if ((uword)q >= (uword)q->s.ptr && ((uword)p > (uword)q ||
  423.             (uword)p < (uword)q->s.ptr))
  424.                break;         /* at one end or the other */
  425.    if ((uword)p + sizeof(HEADER) * p->s.bsize
  426.       == (uword)q->s.ptr) {    /* join to upper */
  427.       p->s.bsize += q->s.ptr->s.bsize;
  428.       if (p->s.bsize * sizeof(HEADER) >= statneed)
  429.          statneed = 0;
  430.       p->s.ptr = q->s.ptr->s.ptr;
  431.       }
  432.    else
  433.       p->s.ptr = q->s.ptr;
  434.    if ((uword)q + sizeof(HEADER) * q->s.bsize ==
  435.       (uword)p) {        /* join to lower */
  436.          q->s.bsize += p->s.bsize;
  437.          if (q->s.bsize * sizeof(HEADER) >= statneed)
  438.             statneed = 0;
  439.          q->s.ptr = p->s.ptr;
  440.          }
  441.    else
  442.       q->s.ptr = p;
  443.    allocp = q;
  444.    }
  445.